I. Field
The present invention relates generally to computing systems, and more particularly, to methods and apparatus for providing continuation passing in a virtual machine to provide efficient program flow and memory resource utilization.
II. Description of the Related Art
Advances in technology have resulted in smaller and more powerful wireless devices. For example, there currently exist a variety of portable wireless telephones, personal digital assistants (PDAs), and paging devices that are small, lightweight, and can be easily carried by users. Typically, these devices include an embedded controller with limited memory resources. For example, the amount of available memory may be limited by the small size of the device.
As wireless devices have become more widespread, there is an increasing need for these devices to handle larger amounts of data and to execute programs that are more sophisticated. For example, users are demanding remote access to interactive programs, such as gaming programs, that require wireless devices to provide fast and efficient communication with remote service providers using a wireless network. In addition, users would like to have remote access to specific programs that are typically accessible on larger home or office systems.
In order to meet these demands, device and service providers have the choice of developing their own technology or trying to make use of existing technology. Unfortunately, developing new technology is both time consuming and expensive, and therefore, an unattractive alternative. To use existing technology, such as existing software, compatibility problems must be overcome. For example, software developed for one processing system may not be compatible with another processing system. Thus, compatibility problems need to be addressed when porting software from one or more systems to run on a wireless device.
One technique used to overcome compatibility problems involves the use of a virtual machine (VM). A typical VM comprises software executing on a host system that allows the host system to run non-native program instructions written for some other system (i.e., a remote system). For example, the non-native program instructions written to execute on the remote system are interpreted by the VM software running on the host system. Thus, a VM running on a wireless device allows the device to run software written for various different systems, thereby allowing device developers and service providers to use existing software to provide added functionality to wireless device users.
Unfortunately, implementing a VM on a resource limited wireless device raises other problems. For example, most VM implementations employ a stack for temporary storage that may be used as a scratch pad to store constants, variables, arguments to called procedures, or other information needed for program execution. During bytecode execution, it is possible to encounter a dynamic function that creates an activation record or context, which may include stack pointers, current program counter (PC), code pointers, etc. A closure or block is a bytecode fragment that refers to elements on the stack in the current context (from where the block was created.) Blocks can be returned from contexts to be used elsewhere in application code. An example is a sort block passed to a sorting function. In order to execute the block at a later stage, the creating context cannot be released, i.e., the creating function cannot return. The block can only be passed to function calls made from the creating function. However, being able to return a parameterized block (i.e., a block that refers to data in the creating context) would be extremely useful.
Some systems solve this problem by creating a completely new stack for each activation record. Since the maximum stack size for each activation record can be computed at compile-time, the stack size is bounded. While this technique seems to solve the problem, it penalizes every function call with stack creation and parameter copying, which is costly on systems with low processing power and limited memory, such as a wireless device. Others techniques allow the return of the creating activation record only if the block does not refer to any actual data in the creating activation record (i.e. the block is clean). This technique solves part of the problem, but does not allow the block to be parameterized with data that was available in the creating context.
Therefore, what is needed is a VM for use in a resource-limited wireless device to provide continuation passing to allow a return of a parameterized block that refers to data in the creating context, thereby providing fast program execution while efficiently utilizing the available memory resources.